package com.xigua._查找;

import java.util.Arrays;

/**
 * @author LiRongHua
 * @version 1.0.0
 * @ClassName _209_长度最小的子数组.java
 * @Description 给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 * @createTime 2022年04月07日 21:54:00
 */
public class _209_长度最小的子数组 {

    public static void main(String[] args) {
        minSubArrayLen1(7,new int[]{2,3,1,2,4,3});
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        if (length == 1) return nums[0] >= target ? 1 : 0;
        int sums[] = new int[length+1];
        sums[0] = 0;
        for (int i = 1; i < length; i++) {
            sums[i] = sums[i-1]+nums[i];
        }
        if (sums[length-1] < target) return 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < sums.length; i++) {
            int s = target + sums[i - 1];
            int bound = Arrays.binarySearch(sums, s);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= length) {
                ans = Math.min(ans, bound - (i - 1));
            }

        }

        return ans == Integer.MAX_VALUE ? 0: ans;
    }

    public static int minSubArrayLen1(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

}
